package history.binarySearch;

/**
 * @author czt
 * @version 1.0
 * @since 2024/10/23
 */
public class BinarySearchBasic {

    public static void main(String[] args) {
        int[] a = {2, 7, 9, 12, 34, 37};
        int target = 7;
        int index = binarySearchBasic(a, target);
        System.out.println("index = " + index);
    }

    //基础版
    public static int binarySearchBasic(int[] a, int target) {
        int i= 0, j= a.length - 1;
        while (i <= j) {
            //int m = (i + j) / 2;
            int m = (i + j) >>> 1;//在二进制中，右移一位相当于除以2；可以防止当m过大导致计算不准确，除法不会动符号位
            if (a[m] > target) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }

        return -1;
    }

    //二分查找改动版
    public static int binarySearchAlternative(int[] a, int target) {
        int i= 0, j= a.length;     //改动1 j在此方法中只作为边界，目标值永远不可能a[j]，但还有可能等于a[i]
        while (i < j) {            //改动2
            //int m = (i + j) / 2;
            int m = (i + j) >>> 1; //在二进制中，右移一位相当于除以2；可以防止当m过大导致计算不准确，除法不会动符号位
            if (a[m] > target) {
                j = m;             //改动3
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}
